package com.g01.by;

import com.g01.qt.Node;

import java.util.HashSet;
import java.util.Stack;

public class FirstCommonNode {
    public static void main(String[] args) {
        // 这里给一个测试用例 a,b 为存在公共节点的两个链表
        Node common = new Node(11);
        common.setNext(new Node(12));
        common.getNext().setNext(new Node(13));
        Node a = new Node(1);
        a.setNext(new Node(2));
        a.getNext().setNext(common);
        Node b = new Node(5);
        b.setNext(new Node(6));
        b.getNext().setNext(new Node(7));
        b.getNext().getNext().setNext(common);
        /*
         *     a:    1->2--v
         *                 11->12->13->
         *     b: 5->6->7--^
         */
        Node result = FindFirstCommonNode.useSet(a, b);
        System.out.println(result);
        result = FindFirstCommonNode.useStack(a, a);
        System.out.println(result);
    }
}

/**
 * 查找两个链表第一个公共节点
 */
class FindFirstCommonNode {
    // 用集合解决
    static Node useSet(Node a, Node b) {
        HashSet<Node> set = new HashSet<>();
        // 先遍历第一个链表
        while (a != null) {
            set.add(a);
            a = a.getNext();
        }
        // 遍历第二个链表进行查找
        while (b != null) {
            if (set.contains(b)) {
                return b;
            }
            b = b.getNext();
        }
        return null;  // 没有公共节点
    }

    // 用栈来解决
    static Node useStack(Node a, Node b) {
        // 申明两个栈用来存储两个链表的值
        Stack<Node> as = new Stack<>();
        Stack<Node> bs = new Stack<>();
        // 链表入栈
        while (a != null) {
            as.push(a);
            a = a.getNext();
        }
        while (b != null) {
            bs.push(b);
            b = b.getNext();
        }
        // 出栈对比，如果不一样，那上一个出栈节点就是第一个公共节点
        Node preOut = null;
        while (!as.isEmpty() && !bs.isEmpty()) {
            if (as.peek() == bs.peek()) {  // 栈顶相同
                preOut = as.pop();
                bs.pop();
            } else {
                break;
            }
        }
        return preOut;
    }
}
